import functools
class Solution(object):
    def minimumDeleteSum(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: int
        """
        n1 = len(s1)
        n2 = len(s2)
        @functools.cache
        def search(i, j):
            if i < 0:
                if j < 0:
                    return 0
                else:
                    return search(i, j - 1) + ord(s2[j])
            else:
                if j < 0:
                    return search(i - 1, j) + ord(s1[i])
                else:
                    if s1[i] == s2[j]:
                        return search(i - 1, j - 1)
                    else:
                        return min(search(i - 1, j) + ord(s1[i]), search(i, j - 1) + ord(s2[j]))

        return search(n1 - 1, n2 - 1)
